//-----------------------深度优先遍历DFS-----------------------------
#include "DFS_BFS_Traverse_MGraph.h"
//访问标志数组
int visited[MAX_VERTEX_NUM]; //用于区分是否已经访问了

//函数变量
Status (*VisitFunc)(int v);

/**
 * @brief 元素访问函数
 * @param int v 被访问的顶点v
 * @retval 状态码，操作成功返回OK，操作失败返回ERROR
 */
Status Print(int v) {

  //设置元素访问方式为控制台打印
  printf(" %3d ", v);

  //操作成功
  return OK;
} // Print

/**
 * @brief 从第v个顶点出发递归地深度优先遍历图G
 * @param MGraph G 图G
 * @param int v 从序号为v的顶点出发
 * @retval 无
 */
void DFS(MGraph G, int v) {
  visited[v] = TRUE;

  VisitFunc(G.vexs[v]); //前提是这个函数指针应该是被赋值了的

  for (int w = FirstAdjVex(G, G.vexs[v]); w >= 0;
       w = NextAdjVex(G, G.vexs[v], G.vexs[w])) {

    //对v的尚未被访问的邻接点w递归调用DFS
    if (!visited[w]) {
      DFS(G, w);
    } // if
  }   // for
} // DFS

/**
 * @brief 对图G作深度优先遍历,调用Visit()函数访问结点
 * @param MGraph G 图G
 * @param Status (*Visit)(int v) 函数指针，指向元素访问函数
 * @retval 无
 */
void DFSTraverse(MGraph G, Status (*Visit)(int v)) {

  VisitFunc = Visit; //通过全局变量在函数之间传值  主要是和DFS之间

  //预置标志数组visited所有值为FALSE
  for (int v = 0; v < G.vexnum; v++) {
    visited[v] = FALSE;
  } // for

  /**
   * 深度优先遍历主循环
   * 写成循环是为了保证在图分为多个连通分量时能对
   * 每个连通分量进行遍历
   */
  for (int v = 0; v < G.vexnum; v++) {
    //若该顶点未被访问，则调用DFS()访问该节点
    if (!visited[v]) {
      DFS(G, v);
    } // if
  }   // for
} // DFSTraverse

//----------------广度优先遍历 (需要使用队列)BFS------------
//说明：队列的相关代码包含在"SqQueue.cpp"中，关于队列的详细方法请阅读该文件

/**
 * @brief 按广度优先非递归遍历图G，使用辅助队列Q和访问标志数组visited
 * @param MGraph G 图G
 * @param Status (*Visit)(int v) 函数指针，指向元素访问函数
 * @retval 无
 */
void BFSTraverse(MGraph G, Status (*Visit)(int v)) {
  int u;

  //广度优先遍历使用到遍历
  SqQueue Q;

  for (int v = 0; v < G.vexnum; v++) {

    visited[v] = FALSE;
  } // for
    //初始化辅助队列Q，得到一个空队列
  InitQueue_Sq(Q);

  //广度优先遍历主循环
  for (int v = 0; v < G.vexnum; v++) {
    // v尚未访问
    if (!visited[v]) {

      visited[v] = TRUE;
      Visit(G.vexs[v]); //就是他自己
      InsertQueue_Sq(Q, v);

      while (!QueueEmpty_Sq(Q)) {
        DeleteQueue_Sq(Q, u); //

        for (int w = FirstAdjVex(G, G.vexs[u]); w >= 0;
             w = NextAdjVex(G, G.vexs[u], G.vexs[w])) {

          if (!visited[w]) {
            visited[w] = TRUE;
            Visit(G.vexs[w]);
            InsertQueue_Sq(Q, w);
          } // if
        }   // for
      }     // while
    }       // if
  }         // for

  DestroyQueue_Sq(Q);
} // BFSTraverse  这个函数得和采用邻接表存储的函数对比一下
